package 中等.搜索.记忆化搜索;

/**
 * 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，
 * 其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的
 * 格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。
 * 你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
 * 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
 * 请你返回从左上角走到右下角的最小 体力消耗值 。
 *
 * @ https://leetcode.cn/problems/path-with-minimum-effort/description/?envType=daily-question&envId=2023-12-11
 * @date 2023/12/16
 */
public class 最小体力消耗路径_1631 {

    public static void main(String[] args) {

    }

    private int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  //定义四个方向，上下左右

    private boolean[][] visited;

    /**
     * 二分枚举答案
     * 假设最小体力消耗值为 x，可以深度搜索或者广度搜索判断是否可以
     * 从左上角走到右下角，x 越大越容易到达，查询 x 的最小值
     */
    public int minimumEffortPath(int[][] heights) {
        int minPath = Integer.MAX_VALUE;
        int left = 0, right = 1_000_000;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            visited = new boolean[heights.length][heights[0].length];
            if (dfs(heights, 0, 0, mid)) {
                minPath = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return minPath;
    }

    private boolean dfs(int[][] heights, int i, int j, int target) {
        int rows = heights.length, columns = heights[0].length;
        if (i == rows - 1 && j == columns - 1) {
            return true;
        }

        boolean ans = false;
        for (int[] direct : direction) {
            int nextI = i + direct[0], nextJ = j + direct[1];

            if (nextI >= 0 && nextI < rows &&
                    nextJ >= 0 && nextJ < columns &&
                    Math.abs(heights[nextI][nextJ] - heights[i][j]) <= target &&
                    !visited[nextI][nextJ]) {

                visited[nextI][nextJ] = true;

                ans = ans || dfs(heights, nextI, nextJ, target);

            }
        }

        return ans;
    }


}
